/*
 * @lc app=leetcode.cn id=543 lang=golang
 *
 * [543] 二叉树的直径
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func diameterOfBinaryTree(root *TreeNode) int {
	diameter := 0
	var helper func(root *TreeNode) int
	helper = func(root *TreeNode) int {
		if root == nil {
			return -1
		} else if root.Left == nil && root.Right == nil {
			return 0
		} else {
			left := 1 + helper(root.Left)
			right := 1 + helper(root.Right)

			diameter = max(diameter, left+right)
			return max(left, right)
		}
	}
	helper(root)
	return diameter
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

// @lc code=end

